This invention relates to machine vision, and particularly to methods and apparatuses for interpretation of edge point data from an image.
Dispersion of data is a common problem in many fields, including image processing. In image processing, data fails to converge to one grouping for numerous reasons, such as, imperfections in the imaging environment, the algorithm(s) employed, and/or the discrete nature of processing the data using a computer. Data dispersion detrimentally affects some types of image processing more than others. For instance, finding lines in images is more detrimentally effected by dispersion than finding regions. Typically, the integrity of smaller groupings of data, such as lines, relative to the remainder of the image, suffer more from dispersion effects. It is also difficult to identify elements composed of a relatively small amount of data because of confusing appropriate data with superfluous data.
An example of dispersion of edge points of a line is illustrated using FIG. 1, not drawn to scale, which depicts an imaged line 102 having multiple edge-point directions 100, shown schematically. An edge point is derived from underlying image pixels, where an image pixel is a picture element characterized by a grey value, where an image can be represented as an array of image pixels. A plurality of connected edge points creates a contour, such as a line or boundary 200 between two regions 202 and 204, illustrated in FIG. 2. The direction of an edge point 210 is perpendicular to the line 200 upon which the edge point 208 resides. Turning back to FIG. 1, the edge points 110 of the line 102 do not share a common direction 100, but are distributed about a peak angle, as shown in the discrete-angle histogram 104. The edge-point directions 100 fall into multiple discrete bins 108 that are distributed around a peak bin 106, where the peak bin 106 represents the mode of the histogram (i.e. the primary direction of the edge points 110 in the line 102). The lack of convergence of all the edge points 110 to the peak bin 106 illustrates the typical data dispersion present for lines in images. Lines detected using the Hough line-transform method also suffer from this problem.
The majority of line finding algorithms in machine-vision applications, are variations of the Hough line-transform method, described in U.S. Pat. No. 3,069,654. The Hough line-transform method transforms characteristics of edge points into line characteristics, and represents the line characteristics on a Hough space, where a point in the Hough space represents a line.
The characteristics of the edge points include the edge-point position, denoted (x, y), edge-point direction, denoted xcex8, and optionally, edge-point magnitude, denoted M, which are all measured in Cartesian space. The edge-point position is typically a function of the position of a neighborhood of the underlying image pixels. The edge-point magnitude and direction are a function of the change in grey value of the image pixels that contribute to the edge point.
The characteristics of an edge point, (xcex8, x, y, and optionally M) are transformed into line characteristics (d, c, and xcex1) Typically, the characteristics of edge points in a contour are called features (such as position), while characteristics derived from the features are called parameters (such as line angle).
The line characteristics are illustrated in Cartesian space in FIG. 3. The line characteristics include a line angle 302, denoted xcex1, which is the angle of the line 300 from the horizontal, a distance-vector 304, denoted d, which is the shortest distance from the origin of a coordinate system 314 to the line 300, and, optionally, a collinear distance 306, denoted c, which is the distance from the edge point 308 to the place where d touches the line 300, in Cartesian space, d is signed to differentiate between lines with identical xcex1 and d parameters on opposite sides of the origin 314. More specifically, the sign of d is negative if the angle 312 of d from the horizontal in Cartesian coordinates is less than 180xc2x0 and greater than, or equal to, zeros (i.e., 180xc2x0 greater than xcex2xe2x89xa70); and positive when the angle 312 of d is less than 360xc2x0, and greater than, or equal to, 180xc2x0 (i.e., 360xc2x0 greater than xe2x8ax96xe2x89xa7180xc2x0).
d, c, and xcex1 are generated from the following Hough-transform equations:
xe2x80x83d =xxc2x7sin(xcex8)xe2x88x92yxc2x7cos(xcex8)xe2x80x83xe2x80x83[1]
c =xxc2x7cos(xcex8)+yxc2x7sin(xcex8)xe2x80x83xe2x80x83[2]
xcex1degrees=[xcex8+90]mod180xe2x80x83xe2x80x83[3]
d and xcex1 are stored on a Hough space.
FIG. 4A depicts an instance of a Hough space 400 for lines. The Hough space for lines is a two-dimensional space in which lines from an image are recorded. The Hough space is adequately represented as a two-dimensional array of bins 402. One axis 404 represents the line-angle, xcex1, and the other axis 406 represents the distance vectors, d. A point on a Hough space represents a line.
During the transformation, for each edge point in an input image: the values of d and xcex1 are calculated, and the bin of the Hough space, whose range includes the value of d and xcex1 for each edge point, is incremented. Once all the edge points in the input image have been examined, the Hough space is searched for maximum values, using peak detection, a method known in the art. The bin having the highest value in the Hough space represents the strongest line detected in the input image, the second highest local maxima represents the second strongest line detected, and so forth.
Each bin 402 in the Hough space represents a discrete range of angles and a discrete range of distance vectors. FIG. 5 shows an instance of a quantization of the angles for a Hough space, where 360xc2x0 is divided into 64 bins. Each of the 64 bins has a range of 5.62 degrees per bin, where the first bin accommodates the angles within 0-5.62xc2x0, the second bin accommodates the angles within 5.62xc2x0-11.24xc2x0, and so on.
Typically, the line-angle range and/or distance-vector range for each bin in the Hough space, and the divisions of ranges between the bins, are driven by system and application parameters, and often do not exactly represent the line angles or distance vectors in a given image. Thus, the partitioning of the line angle and the distance vector into discrete bins hinders detecting lines whose edge points straddle the boundaries, such as lines with a line angle of 5.62xc2x0, in the above example. The edge points of such lines, typically, transform into more than one bin, thus, it is more difficult to detect these lines, as is further discussed in J. Brian Burns, Allen R. Hanson, and Edward M. Riseman, xe2x80x9cExtracting Straight Linesxe2x80x9d, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(4), 1986.
The effects of dispersion and the number of partitions in an axis are decreased by increasing the range of data accepted in each bin. However, increasing the range decreases precision of the line angles and/or distance vectors. As illustrated using FIG. 6, which depicts a 59xc2x0 line 600 and a 51xc2x0 line 610 and their respective discrete-angle histograms 602 and 612 derived from a Hough space. A Hough space created using a four-bit representation for angle partitions the line-angle axis of the Hough space so that the edge points 604 and 614 of both lines 600 and 610 all map to bin two in the Hough space. Thus, the ability is lost to distinguish between a 51xc2x0 line and 59xc2x0 line in Hough space.
Other techniques known in the art, such as a Point Spread Function update method, for example, also decrease dispersion effects. For each edge point, the Point Spread Function update method increments more than one bin with a partial weighting. Although the edge points do not contribute 100% to the weight of the appropriate bin, it is less likely any edge points fail completely to contribute to the weight of the appropriate bin. Although the Point Spread Function update method compensates, in part, for dispersion, it also causes a loss of precision because the Point Spread Function tends to smear the Hough space peaks.
An additional problem with image processing smaller contours is the inability to identify appropriate groupings of edge points of each contour given the superfluous noise and background clutter. The paper W. Eric L. Grimson and Daniel P. Huttenlocher xe2x80x9cOn the Sensitivity of the Hough Transform for Object Recognition,xe2x80x9d Transactions on Pattern Analysis and Machine Intelligence, 12(3), 1990, discusses how line finding and object detection using Hough transforms suffers from superfluous noise and background clutter, particularly when trying to detect shorter lines.
Also, the Hough transform is only as precise as the underlying edge-point data, which is limited according to current technology. Further, the precision cannot be greatly increased by interpolating the edge-point data to a higher number of bits because, eventually, the interpolated bits do not represent meaningful precision.
The invention provides methods and apparatuses for refining a parameter of a contour in an image. The contour is represented on a first parameter space and a second parameter space, where the first parameter space and the second parameter space are defined by a plurality of parameter axes, each of the parameter axes represents a contour 5 parameter and has bins adapted to receive edge points. The first parameter space and the second parameter space are offset from one another along one of the plurality of parameter axes. To represent the contour on the first parameter space and the second parameter space, first, a plurality of contour parameters are calculated for each edge point of an image. Next, bins of the first parameter space and the second parameter space are filled with the same edge points (i.e. data) according to the plurality of contour parameters. Then, the first parameter space and the second parameter space are merged to create the hybrid space, where each of the edge points is represented once in the hybrid space. Thus, the hybrid space allows refinement of the parameter represented on the first dimension because of the offset and the merging.
For instance, in a preferred embodiment, the parameter refined is the line angle of a line contour represented on a Hough space. First, the direction of the edge points, which is an example of an edge-point feature, is used in a Hough line transformation to calculate the line angle, which is an example of a contour parameter. The line angle is represented as discrete bins on one axis of a first Hough parameter space and one axis of a second Hough parameter space that are offset from one another along the line-angle axis by one-half of a bin. Each edge point is represented in one bin of the first Hough parameter space and one bin of the second Hough parameter space. One of the bins (either on the first Hough parameter space or the second Hough parameter space) for each edge point is a better representation of the contour parameter, for that edge point and/or for the contour of which the edge point is a member. Accordingly, those bins (i.e., a sub-set of bins from the first Hough space and a sub-set of the bins from the second Hough space) are chosen to be merged to form one hybrid space having each of the edge points represented therein substantially only once. Thus, the line-angle parameter of the contour is refined because the edge points that yield two adjacent line angle parameter values in one of the Hough spaces converge to a single line angle parameter value in the other Hough space, and the bin to which the edge points converge is selected to be included in the hybrid space.
Among other advantages the invention recovers edge points that are otherwise split across parameter space bins due to quantization effects by providing two offset mapping schemes for parameters generated for each edge point, and then using in a single hybrid space the more appropriate mapping for each bin.
The invention overcomes various problems with the prior art, including, but not limited to, minimizing the effect of, and decreasing the extent of, dispersion of edge points; de-emphasizing the effect of quantizing ranges of features of edge points or quantizing ranges of parameters derived from features of edge points; and finding a line that straddle boundaries between the edge-point quantizations in a Hough space.